\chapter{信息论的几个基本概念}

\section{基本概念}

\begin{definition}{熵(Encropy)}{def-encropy}\cite{ele-InformationTheory}
	离散随机变量$\mathbb{X}$的熵记为$H(\mathbb{X})$,定义为:
	\[H(\mathbb{X})=-\sum_{x\in X} {Pr(x)\log{Pr(x)}}\]	
	其中$\log$是以2为底，单位为bit(比特)。
\end{definition}

\vspace{0.5cm}
\begin{example}
	我们看看掷骰子，其采样空间$\Omega=\{head,tail\}$,head表示正面，tail表示反面，我们有$Pr(head)=\dfrac{1}{2},Pr(tail)=\dfrac{1}{2}$，我们定义一个随机变量$\mathbb{X}$(也就是定义一个函数):\footnote{在此为了便于理解，不与后面0,1编码搞混，我们这里的函数值定义为6,7。}
	\[\mathbb{X}(w)=\begin{cases}
	6,w=head \\
	7,w=tail
	\end{cases}\]
	我们有$Pr(\mathbb{X}=6)=\dfrac{1}{2},Pr(\mathbb{X}=7)=\dfrac{1}{2}$,那么随机变量$\mathbb{X}$的熵为：
	\[H(\mathbb{X})=-(Pr(6)\log{Pr(6)}+Pr(7)\log{Pr(7)})=-(\frac{1}{2}\times(-1)+\frac{1}{2}\times(-1)) =1(bit)\]
	从这个例子我们也可以看到随机变量$\mathbb{X}$映射到什么样的实数值并不影响它的熵。\par
	对于这个随机变量的取值，我们可以分别用0,1进行编码，也就是1bit的长度。
	
\end{example}
\vspace{0.5cm}

\begin{definition}{联合熵(Joint Encropy)}{def-jointencropy}\cite{ele-InformationTheory}
	离散随机变量$\mathbb{X}$和$\mathbb{Y}$的，其联合概率分布记为$Pr(x,y)$，那么其联合熵记为$H(\mathbb{X},\mathbb{Y})$,定义为:
	\[H(\mathbb{X},\mathbb{Y})=-\sum_{x\in X}\sum_{y\in Y} {Pr(x,y)\log{Pr(x,y)}}\]	
	其中$\log$是以2为底，单位为bit(比特)。
\end{definition}


\begin{definition}{条件熵(Conditional Encropy)}{def-condencropy}\cite{ele-InformationTheory}
	离散随机变量$\mathbb{X}$和$\mathbb{Y}$的，其联合概率分布记为$Pr(x,y)$，那么条件熵$H(\mathbb{Y}|\mathbb{X})$定义为:
	\[H(\mathbb{Y}|\mathbb{X}) =-\sum_{x\in X}\sum_{y\in Y} {Pr(x,y)\log{Pr(y|x)}} 
	                           =\sum_{x\in X}Pr(x)H(\mathbb{Y}|\mathbb{X}=x) \]	
	其中$\log$是以2为底，单位为bit(比特)。
\end{definition}

\section{哈夫曼编码(Huffman Coding)}

我们用一个例子来解释哈夫曼编码，并且来解释其为什么称为最优编码？以及最优的评价视角。

我们有一个离散随机变量$\mathbb{X}$，有四个函数值$\{a,b,c,d\}$(为了便于后面描述，我们就认为其函数值为这四个字母),并且其概率为$Pr(a)=0.05,Pr(b)=0.1,Pr(a)=0.25,Pr(a)=0.6,$下面我们对这四种情况进行编码。

\textbf{方法一：}每遇到一个1，表示开始一个字母开始，依次用后面0的个数表示不同字母，此方法记为f：
\[f(a)=1\quad f(b)=10\quad f(c)=100\quad f(d)=1000\quad\]


\textbf{方法二：}用连续1的个数表示不同字母，此方法记为g：
\[g(a)=0\quad g(b)=10\quad g(c)=110\quad g(d)=111\quad\]

\textbf{方法三：}哈夫曼编码是根据概率的大小依次编码，基本思路是概率大的编码长度短，概率小的编码长度长，我们用图\ref{}来表示编码过程.\\
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{HuffmanCoding.png}
	\caption{哈夫曼编码过程(二叉树示例)}
	\label{fig:HuffmanCoding}
\end{figure}

此方法记为h：
\[h(a)=000 \quad h(b)=001 \quad h(c)=01 \quad h(d)=1\]

我们使用编码的概率加权平均长度来表示编码的效率，此平均长度
$\mathbf{l}(f)=\sum_{x\in X}Pr(x)\|f(x)\|$,
其中f表示编码方法，$|f(x)|$表示编码后二进制串长度。

那么依次计算三种编码方法的平均长度：
\[\mathbf{l}(f)=0.05\times 1+0.1\times 2+0.25\times 3+ 0.6\times 4=3.4 \]
\[\mathbf{l}(g)=0.05\times 1+0.1\times 2+0.25\times 3+ 0.6\times 3=2.8 \]
\[\mathbf{l}(h)=0.05\times 3+0.1\times 3+0.25\times 2+ 0.6\times 1=1.55 \]
我们计算一下这个随机变量的熵：
\[H(\mathbb{X})=-(0.05\times \log{0.05} + 0.1\times \log{0.1}+0.25\times \log{0.25}+0.6\times \log{0.6)}\approx 1.49 \]

可见哈夫曼编码的平均长度与熵最接近。

可以证明: $H(\mathbb{X}) \leq \mathbf{l}(\mathbb{X}\text{的哈夫曼编码}) \leq H(\mathbb{X})+1 $.

\section{熵的几个性质}

\begin{theorem}{熵的上限}{theo-entro-max}
	假设$\mathbb{X}$是一个随机变量，概率分布为$p_1,p_2,\ldots,p_n$，其中$p_i>0,1\leq i\leq n$，那么$H(\mathbb{X})\leq \log_2{n}$，当且仅当$p_i=\dfrac{1}{n},1\leq i\leq n$时，等号成立。
\end{theorem}
这个定理的证明用到了Jensen不等式，具体证明可参考\cite{密码学原理与实践}。


\begin{theorem}{联合熵上限}{theo-jointentro-max}\footnote{定理具体证明见\cite{密码学原理与实践}。}
	假设$\mathbb{X},\mathbb{Y}$是两个随机变量，那么$H(\mathbb{X},\mathbb{Y}) \leq H(\mathbb{X})+H(\mathbb{Y})$，当且仅当$\mathbb{X},\mathbb{Y}$统计独立时，等号成立。
\end{theorem}
